Equivalence class

 ( Algebra ) 

In mathematics, when the elements of some set $S$ have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set $S$ into equivalence classes. These equivalence classes are constructed so that elements $a$ and $b$ belong to the same equivalence class if, and only if, they are equivalent.

Formally, given a set $S$ and an equivalence relation $\backslash sim$ on $S,$ the of an element $a$ in $S$ is denoted $a$ or, equivalently, $a\_\{\backslash sim\}$ to emphasize its equivalence relation $\backslash sim$, and is defined as the set of all elements in $S$ with which $a$ is $\backslash sim$-related. The definition of equivalence relations implies that the equivalence classes form a partition of $S,$ meaning, that every element of the set belongs to exactly one equivalence class. The set of the equivalence classes is sometimes called the quotient set or the quotient space of $S$ by $\backslash sim,$ and is denoted by $S\; /\{\backslash sim\}.$

When the set $S$ has some structure (such as a group operation or a topology) and the equivalence relation $\backslash sim$ is compatible with this structure, the quotient set often inherits a similar structure from its parent set. Examples include quotient spaces in linear algebra, quotient spaces in topology, , homogeneous spaces, , , and quotient categories.

---

Definition and notation An equivalence relation on a set $X$ is a binary relation $\backslash sim$ on $X$ satisfying the three properties:

• $a\; \backslash sim\; a$ for all $a\; \backslash in\; X$ (reflexivity),
• $a\; \backslash sim\; b$ implies $b\; \backslash sim\; a$ for all $a,\; b\; \backslash in\; X$ (symmetry),
• if $a\; \backslash sim\; b$ and $b\; \backslash sim\; c$ then $a\; \backslash sim\; c$ for all $a,\; b,\; c\; \backslash in\; X$ (transitivity).

The equivalence class of an element $a$ is defined as

$a\; =\; \backslash \{\; x\; \backslash in\; X\; :\; a\; \backslash sim\; x\; \backslash \}.$

The word "class" in the term "equivalence class" may generally be considered as a synonym of "set", although some equivalence classes are not sets but . For example, "being isomorphic" is an equivalence relation on groups, and the equivalence classes, called isomorphism classes, are not sets.

The set of all equivalence classes in $X$ with respect to an equivalence relation $R$ is denoted as $X\; /\; R,$ and is called $X$ modulo $R$ (or the ' of $X$ by $R$). The surjective map $x\; \backslash mapsto\; x$ from $X$ onto $X\; /\; R,$ which maps each element to its equivalence class, is called the ', or the canonical projection.

Every element of an equivalence class characterizes the class, and may be used to represent it. When such an element is chosen, it is called a representative of the class. The choice of a representative in each class defines an injection from $X\; /\; R$ to . Since its composition with the canonical surjection is the identity of $X\; /\; R,$ such an injection is called a section, when using the terminology of category theory.

Sometimes, there is a section that is more "natural" than the other ones. In this case, the representatives are called . For example, in modular arithmetic, for every integer greater than , the congruence modulo is an equivalence relation on the integers, for which two integers and are equivalent—in this case, one says congruent—if divides $a-b;$ this is denoted $a\backslash equiv\; b\; \backslash pmod\; m.$ Each class contains a unique non-negative integer smaller than $m,$ and these integers are the canonical representatives.

The use of representatives for representing classes allows avoiding considering explicitly classes as sets. In this case, the canonical surjection that maps an element to its class is replaced by the function that maps an element to the representative of its class. In the preceding example, this function is denoted $a\; \backslash bmod\; m,$ and produces the remainder of the Euclidean division of by .

---

Properties For a set $X$ with an equivalence relation $\backslash sim$, every element $x$ of $X$ is a member of the equivalence class $x$ by reflexivity ($a\; \backslash sim\; a$ for all $a\; \backslash in\; X$). Every two equivalence classes $x$ and $y$ are either equal if $x\; \backslash sim\; y$, or disjoint sets otherwise. Therefore, the set of all equivalence classes of $X$ forms a partition of $X$: every element $x$ of $X$ belongs to one and only one equivalence class.

Conversely, for a set $X$, every partition comes from an equivalence relation in this way, and different relations give different partitions. Thus $x\; \backslash sim\; y$ if and only if $x$ and $y$ belong to the same set of the partition.

It follows from the properties in the previous section that if $\backslash ,\backslash sim\backslash ,$ is an equivalence relation on a set $X,$ and $x$ and $y$ are two elements of $X,$ the following statements are equivalent:

• $x\; \backslash sim\; y$,
• $x\; =\; y$, and
• $x\; \backslash cap\; y\; \backslash ne\; \backslash emptyset.$

---

Examples

• Let $X$ be the set of all rectangles in a plane, and $\backslash ,\backslash sim\backslash ,$ the equivalence relation "has the same area as", then for each positive real number $A,$ there will be an equivalence class of all the rectangles that have area $A.$
• Consider the modulo 2 equivalence relation on the set of , $\backslash Z,$ such that $x\; \backslash sim\; y$ if and only if their difference $x\; -\; y$ is an even number. This relation gives rise to exactly two equivalence classes: one class consists of all even numbers, and the other class consists of all odd numbers. Using square brackets around one member of the class to denote an equivalence class under this relation, $7,\; 9,$ and $1$ all represent the same element of $\backslash Z\; /\{\backslash sim\}.$
• Let $X$ be the set of of integers $(a,\; b)$ with non-zero $b,$ and define an equivalence relation $\backslash ,\backslash sim\backslash ,$ on $X$ such that $(a,\; b)\; \backslash sim\; (c,\; d)$ if and only if $a\; d\; =\; b\; c,$ then the equivalence class of the pair $(a,\; b)$ can be identified with the rational number $a\; /\; b,$ and this equivalence relation and its equivalence classes can be used to give a formal definition of the set of rational numbers. The same construction can be generalized to the field of fractions of any integral domain.
• If $X$ consists of all the lines in, say, the Euclidean plane, and $L\; \backslash sim\; M$ means that $L$ and $M$ are parallel lines, then the set of lines that are parallel to each other form an equivalence class, as long as a line is considered parallel to itself. In this situation, each equivalence class determines a point at infinity.

---

Graphical representation An undirected graph may be associated to any symmetric relation on a set $X,$ where the vertices are the elements of $X,$ and two vertices $s$ and $t$ are joined if and only if $s\; \backslash sim\; t.$ Among these graphs are the graphs of equivalence relations. These graphs, called , are characterized as the graphs such that the connected components are cliques.

---

Invariants If $\backslash ,\backslash sim\backslash ,$ is an equivalence relation on $X,$ and $P(x)$ is a property of elements of $X$ such that whenever $x\; \backslash sim\; y,$ $P(x)$ is true if $P(y)$ is true, then the property $P$ is said to be an invariant of $\backslash ,\backslash sim\backslash ,,$ or well-defined under the relation $\backslash ,\backslash sim.$

A frequent particular case occurs when $f$ is a function from $X$ to another set $Y$; if $f\backslash left(x\_1\backslash right)\; =\; f\backslash left(x\_2\backslash right)$ whenever $x\_1\; \backslash sim\; x\_2,$ then $f$ is said to be $\backslash ,\backslash sim\backslash ,,$ or simply $\backslash ,\backslash sim.$ This occurs, for example, in the character theory of finite groups. Some authors use "compatible with $\backslash ,\backslash sim\backslash ,$" or just "respects $\backslash ,\backslash sim\backslash ,$" instead of "invariant under $\backslash ,\backslash sim\backslash ,$".

Any function $f\; :\; X\; \backslash to\; Y$ is class invariant under $\backslash ,\backslash sim\backslash ,,$ according to which $x\_1\; \backslash sim\; x\_2$ if and only if $f\backslash left(x\_1\backslash right)\; =\; f\backslash left(x\_2\backslash right).$ The equivalence class of $x$ is the set of all elements in $X$ which get mapped to $f(x),$ that is, the class $x$ is the inverse image of $f(x).$ This equivalence relation is known as the kernel of $f.$

More generally, a function may map equivalent arguments (under an equivalence relation $\backslash sim\_X$ on $X$) to equivalent values (under an equivalence relation $\backslash sim\_Y$ on $Y$). Such a function is a morphism of sets equipped with an equivalence relation.

---

Quotient space in topology In topology, a quotient space is a topological space formed on the set of equivalence classes of an equivalence relation on a topological space, using the original space's topology to create the topology on the set of equivalence classes.

In abstract algebra, congruence relations on the underlying set of an algebra allow the algebra to induce an algebra on the equivalence classes of the relation, called a quotient algebra. In linear algebra, a quotient space is a vector space formed by taking a quotient group, where the quotient homomorphism is a linear map. By extension, in abstract algebra, the term quotient space may be used for , , , or any quotient algebra. However, the use of the term for the more general cases can as often be by analogy with the orbits of a group action.

The orbits of a group action on a set may be called the quotient space of the action on the set, particularly when the orbits of the group action are the right of a subgroup of a group, which arise from the action of the subgroup on the group by left translations, or respectively the left cosets as orbits under right translation.

A normal subgroup of a topological group, acting on the group by translation action, is a quotient space in the senses of topology, abstract algebra, and group actions simultaneously.

Although the term can be used for any equivalence relation's set of equivalence classes, possibly with further structure, the intent of using the term is generally to compare that type of equivalence relation on a set $X,$ either to an equivalence relation that induces some structure on the set of equivalence classes from a structure of the same kind on $X,$ or to the orbits of a group action. Both the sense of a structure preserved by an equivalence relation, and the study of invariants under group actions, lead to the definition of invariants of equivalence relations given above.

---

See also

• Equivalence partitioning, a method for devising software test sets based on program coverage of possible inputs
• Homogeneous space, the quotient space of

---

Notes

• Elias M. Stein (2025). 9781400840557, Princeton University Press. ISBN 9781400840557

---

Further reading

Post Comment